import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeMap;

/**
 * Created by L.jp
 * Description:给定一个二叉树，确定他是否是一个完全二叉树。
 * 完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，
 * 其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。
 * User: 86189
 * Date: 2022-06-25
 * Time: 13:20
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
  }
public class Solution {
    public boolean isCompleteTree (TreeNode root) {
        //借助队列判断是不是符合完全二叉树层次遍历的情况，对于完全二叉树的层次遍历就是如果前面出现了空节点，
        // 后面再出现不是空节点的，那么就不是完全二叉树
        
        if(root==null){
            return true;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        boolean hasNullNode=false;
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            //如果当前节点是空节点，那么就标记为已经出现了空节点
            if(cur==null){
                hasNullNode=true;
                continue;
            }
            //如果当前节点不是空节点，那么弹出的时候就再判断前面的节点中是不是出现了空节点
            if(hasNullNode){
                //当前节点不是空节点，且前面已经出现了空节点，那么就不是完全二叉树
                return false;
            }
            //加入当前节点的左右子树再加以判断
            queue.add(cur.left);
            queue.add(cur.right);
        }
        return true;
    }

}
